/**
 * 215. Kth Largest Element In An Array 数组中的第K大元素
 * https://leetcode.com/problems/kth-largest-element-in-an-array/
 */
class KthLargestElementInAnArray {
    int quickselect(int[] nums, int l, int r, int k) {
        if (l == r) return nums[k];
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        if (k <= j) return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }

    /**
     * 方法：快速选择算法
     * 
     * Args:
     *   nums: int[], 输入数组
     *   l: int, 左边界
     *   r: int, 右边界
     *   k: int, 目标位置
     * 
     * Returns:
     *   int: 数组中第k大的元素
     * 
     * Time: O(n), 平均情况下，每次划分将问题规模减半
     * Space: O(logn), 递归调用栈的深度
     */
    public int findKthLargest(int[] _nums, int k) {
        int n = _nums.length;
        return quickselect(_nums, 0, n - 1, n - k);
    }

    /**
     * 方法：最小堆法
     * 
     * Args:
     *   nums: int[], 输入数组
     *   k: int, 目标位置
     * 
     * Returns:
     *   int: 数组中第k大的元素
     * 
     * Time: O(nlogk), 建堆O(k)，每次调整堆O(logk)，共调整n-k次
     * Space: O(1), 原地操作，不需要额外空间
     */
    public int findKthLargest1(int[] nums, int k) {
        int heapSize = nums.length;
        // 前k个元素建堆
        buildMinHead(nums, k);
        // 处理剩余元素
        for(int i = k; i< heapSize; i++){
            if(nums[i] > nums[0]){
                nums[0] = nums[i];
                heapfiy(nums, 0, k);
            }
        }
        return nums[0];
    }

    private void buildMinHead(int[] nums, int size){
        for(int i = size / 2 -1; i >= 0; i--){
            heapfiy(nums, i, size);
        }
    }

    private void heapfiy(int[] nums, int i, int size){
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < size && nums[left] < nums[smallest]){
            smallest = left;
        }
        if (right < size && nums[right] < nums[smallest]){
            smallest = right;
        }
        if (smallest != i){
            swap(nums, i, smallest);
            heapfiy(nums, smallest, size);
        }
    }

    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}